/*
https://leetcode.cn/problems/strange-printer/description/
664. 奇怪的打印机
方钊堉 2024.10.19
区间dp
*/
class Solution {
public:
    int dp[100][100][100];

    // 主函数，调用辅助函数进行动态规划计算
    int strangePrinter(string s) {
        memset(dp, 0, sizeof(dp)); // 初始化动态规划数组
        return getDP(s, 0, s.size() - 1, 0); // 从字符串的第一个字符到最后一个字符开始计算
    }

    // 辅助函数，使用动态规划计算从 l 到 r 区间内打印字符串所需的最少操作次数
    int getDP(string &s, int left, int right, int count) {
        if (left > right) return 0; // 如果区间无效，返回0

        // 如果已经计算过该区间的结果，直接返回
        if (dp[left][right][count]) return dp[left][right][count];

        int right1 = right, count1 = count;
        // 去除右端相同的字符，并更新计数
        while (right1 >= left && s[right1] == s[right]) {
            count1++;
            right1--;
        }

        // 计算去除右端相同字符后的区间所需的操作次数
        dp[left][right][count] = getDP(s, left, right1, 0) + 1;

        // 尝试在区间内找到与右端字符相同的字符，以减少操作次数
        for (int i = left; i <= right1; i++) {
            if (s[i] == s[right]) {
                dp[left][right][count] = min(dp[left][right][count], 
                                             getDP(s, left, i, count1) + getDP(s, i + 1, right1, 0));
            }
        }

        return dp[left][right][count];
    }
};